#include<iostream>


void MaxHeap(int*a,int n,int i)
{
    int left=2*i+1;
    int right =2*i+2;
    int max=i;
    if (left<n&&a[left]>a[max])
    {
        max=left;
    }
    if (right<n&&a[right]>a[max])
    {
        max=right;
    }
    if (max!=i)
    {
        std::swap(a[i],a[max]);
        MaxHeap(a,n,max);
    }
    
}
void HeapSort(int*a,int n)
{
    for (int i = n/2-1; i >=0; i--)
    {
        MaxHeap(a,n,i);
    }
    for (int i = n-1; i>=0; i--)
    {
        std::swap(a[0],a[i]);
        MaxHeap(a,i,0);

    }
}
int main()
{
int a[5]={5,6,1,3,9};
HeapSort(a,5);
for (int i = 0; i < 5; i++)
{
    std::cout<<a[i]<<" ";
    
}
std::cout<<std::endl;
return 0;

}
